The present invention relates to digital communication channels, and more particularly, to a method for efficient interleaving of variable length packets.
In many communication channels, errors appear in bursts, i.e., a single error event has more than one erroneous data element (bit, byte, symbol or other). Error bursts occur because of various reasons, among them burst noise in a channel, error bursts in the output of a Viterbi decoder and others. Error bursts are usually undesirable because most decoders cannot efficiently handle many neighboring errors. An interleaver is a device that allows for the spreading of the error from a burst into separated xe2x80x9csinglexe2x80x9d errors by performing permutations on the data elements. For example, when block coding (such as Reed-Solomon) is used the interleaver allows for spreading of the error burst between a few codewords, thus relaxing the error correction requirements of the code.
A very common and simple interleaver is the block interleaver. In this interleaver, the data elements (bits, bytes, symbols or others) are placed into a two-dimensional table row-wise and are read out of the table column-wise. The block size (i.e., the number of rows multiplied by the number of columns) is typically constrained by the memory resources of the interleaver.
In a packet network, variable-length packets of data are transmitted through a communication channel. The packet size is often greater than the block size. In this case, the packet is divided into segments that are smaller than or equal to the interleaver block size. Each segment is then separately interleaved. A trivial way to perform this segmentation is make all segments but the last one, equal to the interleaver block size. The last segment will then be smaller than the block size. The disadvantage of this method is that the last segment can be very small for certain packet lengths. This results in poor performance of the interleaver.
The present invention provides a method for efficient interleaving of variable-length packets. In packet networks, block interleaving of variable-length packets can be inefficient when the interleaver block size is fixed and smaller than the packet size. The reason is that for certain packet lengths, the remaining number of elements for the last block (i.e., bytes or symbols) can be very low.
The method of the present invention calculates the optimal interleaver block sizes for a known packet length, which may be variable, and a known (or selected) interleaver width size.